import java.util.Arrays;
import java.util.Random;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: mac
 * Date: 2022-10-12
 * Time: 19:36
 */
public class TestDemo {
    //常见排序算法：七个

    //一个稳定的排序，可以实现为不稳定的排序
    //不稳定的排序是不可以变成稳定的排序的

    /**
     * 时间复杂度：
     * 最坏情况：O(n^2)
     * 最好情况：O(n)，最好情况就是有序数据
     * 对于直接插入排序，数据越有序越快——常用于排序优化(快排优化)
     * 空间复杂度：O(1)
     * @param array
     */

    //1.插入排序 - 稳定的排序算法
    public static void insertSort1 (int[] array){
        for (int i = 0; i < array.length; i++) {
            int tmp = array[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if (array[j] > tmp){
                    array[j + 1] = array[j];
                }else{
                    break;
                }
            }
            array[j + 1] = tmp;
        }
    }
     public static void insertSort2 (int[] array, int start, int end){
        for (int i = 1; i < end; i++) {
            int tmp = array[i];
            int j = i - 1;
            for (; j >= start; j--) {
                if (array[j] > tmp){
                    array[j + 1] = array[j];
                }else{
                    break;
                }
            }
            array[j + 1] = tmp;
        }
    }
    //折半插入排序——二分查找——了解

    //思考:假设现在有10000个数据,如果对其进行排序，使用插入排序
    //直接插入排序：最坏时间复杂度：10000 * 10000
    //若采用分组的思想，我们会发现 100 * 100 * 100 = 100w
    //时间复杂度就会有很大的改变

    //2.希尔排序 - 分组思想
    //最后整体看做一组，前面>1的这些组都是预排序

    /**
     * 希尔排序
     * 时间复杂度：n^(1.3~1.5)
     * 空间复杂度：不稳定的
     * 看在比较的过程中是否发生了跳跃式的交换 - 不稳定的排序
     * @param array 待排序序列
     * @param gap 组数
     */
    public static void shell(int[] array, int gap){
        for (int i = 0; i < array.length; i++) {
            int tmp = array[i];
            int j = i - gap;
            for (; j >= 0; j -= gap) {
                if (array[j] > tmp){
                    array[j + gap] = array[j];
                }else{
                    break;
                }
            }
            array[j + gap] = tmp;
        }
    }
    public static void shellSort(int[] array){
        int gap = array.length;
        while (gap > 1) {
            shell(array, gap);
            gap /= 2;
        }
        shell(array, 1);//保证最后为1组
    }

    /**
     * 选择排序 - 优化
     * 时间复杂度 O(n^2)
     * @param array 待排序序列
     */
    public static void swap(int[] array, int i, int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    public static void selectSort(int[] array){
        for (int i = 0; i < array.length; i++) {
            int min = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[min]){
                    min = j;
                }
            }
            swap(array, i, min);
        }
    }
    //双向选择排序 - 了解
    //每一次从区间中选出最小值和最大值并放到最前面和最后面

    //堆排序

    /**
     * 堆排序
     * 时间复杂度：O(n * log N)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     * @param array
     */
    public static void heapSort(int[] array){
        createHeap(array);
        for (int end = array.length - 1; end > 0; end--) {
            swap(array, 0, end);
            shiftDown(array, 0, end);
        }
    }
    public static void createHeap(int[] array){
        for (int parent = (array.length - 2) / 2; parent >= 0; parent--) {
            shiftDown(array,parent,array.length);
        }
    }
    public static void shiftDown(int[] array, int parent, int len){
        int child = 2 * parent + 1;
        while (child < len){
            if (child + 1 < len && array[child] < array[child+ 1]) {
                child++;
            }
            if (array[child] > array[parent]){
                swap(array,child,parent);
                parent = child;
                child = child * 2 + 1;
            }else{
                break;
            }
        }
    }

    /**
     * 冒泡排序
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(1)
     * @param array
     */
    public static void bubbleSort(int[] array){
        for (int i = 0; i < array.length - 1; i++) {
            boolean flg = false;
            for (int j = 0; j < array.length - i - 1; j++) {
                if (array[j] > array[j + 1]){
                    swap(array,j,j + 1);
                    flg = true;
                }
            }
            if (flg == false){//优化
                break;
            }
        }
    }

    /**
     * 快速排序
     * 时间复杂度:
     * 最好：O(k*n*logn) 快排中k小一点
     * 最坏：O(n^2) - 单分支树
     * 空间复杂度:
     * 最好：O(logn)
     * 最坏：O(n)
     * 优化：基准优化 1.随机 2.三数取中法 3.把和基准相同的的数据移到跟前来
     * 4.利用直接插入排序,优化算法
     * 不稳定排序
     * @param array 待排序数组
     */
    public static void quickSort(int[] array){
        quick(array,0, array.length - 1);
    }
    public static void quick(int[] array, int left, int right){
        if (left >= right){
            return;
        }
        if (right - left + 1 <= 1600){
            insertSort2(array, left, right);
            return;
        }
        //1.找基准之前,我们找到中间大小的值
        int midValIndex = findMidValIndex(array, left, right);
        swap(array,midValIndex,left);

        int pivot = partition(array, left, right);
        quick(array, left, pivot - 1);
        quick(array, pivot + 1, right);
    }
    private static int findMidValIndex(int[] array, int start, int end){
        int mid = start + ((end - start) >>> 1);
        if (array[start] < array[end]){
            if (array[mid] < array[start]){
                return start;
            }else if(array[mid] > array[end]){
                return end;
            }else{
                return mid;
            }
        }else{
            if (array[mid] > array[start]){
                return start;
            }else if (array[mid] < array[end]){
                return end;
            }else{
                return mid;
            }
        }
    }
    public static int partition(int[] array, int start, int end){
        int tmp = array[start];
        while (start < end){
            while (start < end && array[end] >= tmp){
                end--;
            }
            array[start] = array[end];
            while (start < end && array[start] <= tmp){
                start++;
            }
            array[end] = array[start];
        }
        array[start] = tmp;
        return start;
    }

    /**
     * 非递归快排
     * @param array
     */
    public static void quickSort1(int[] array){
        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = array.length - 1;
        int pivot = partition(array, left, right);
        if (pivot > left + 1){
            stack.push(left);
            stack.push(pivot - 1);
        }
        if (pivot < right - 1){
            stack.push(pivot + 1);
            stack.push(right);
        }
        while (!stack.isEmpty()){
            right = stack.pop();
            left = stack.pop();
            pivot = partition(array, left, right);
            if (pivot > left + 1){
                stack.push(left);
                stack.push(pivot - 1);
            }
            if (pivot < right - 1){
                stack.push(pivot + 1);
                stack.push(right);
            }
        }
    }

    //给你两个有序数组，合并成一个有序数组

    /**
     * 合并成有序数组
     * @param array1 数组1
     * @param array2 数组2
     * @return
     */
    public static int[] mergeArray(int[] array1, int[] array2){
        int str1 = 0;
        int str2 = 0;
        int str = 0;
        int[] array = new int[array1.length + array2.length];

        while (str1 < array1.length && str2 < array2.length){
            if (array1[str1] < array2[str2]){
                array[str] = array1[str1];
                str1++;
                str++;
            }else{
                array[str] = array2[str2];
                str2++;
                str++;
            }
        }
        while (str1 < array1.length){
            array[str] = array1[str1];
            str1++;
            str++;
        }
        while (str2 < array2.length){
            array[str] = array2[str2];
            str2++;
            str++;
        }
        return array;
    }

    /**
     * 归并排序
     * 时间复杂度：O(n * logn)
     * 空间复杂度：O(n)
     * 稳定性：稳定的排序
     * 稳定的排序算法：插入 归并  冒泡
     * @param array
     */
    public static void mergeSort(int[] array){
        mergeSortInternal(array,0,array.length - 1);
    }

    private static void mergeSortInternal(int[] array, int low, int high){
        if (low >= high){
            return;
        }
        int mid = low + ((high - low) >>> 1);

        mergeSortInternal(array, low, mid);
        mergeSortInternal(array, mid + 1, high);
        merge(array,low,mid,high);
    }
    private static void merge(int[] array,int low, int mid, int high){
        int[] tmp = new int[high - low + 1];
        int k = 0;
        int s1 = low;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = high;
        while (s1 <= e1 && s2 <= e2){
            if (array[s1] < array[s2]){
                /*tmp[k] = array[low];
                low++;
                k++;*/
                tmp[k++] = array[s1++];
            }else{
                /*tmp[k] = array[mid + 1];
                mid+ +;
                k++;*/
                tmp[k++] = array[s2++];
            }
        }
        while (s1 <= e1){
            tmp[k++] = array[s1++];
        }
        while (s2 <= e2){
            tmp[k++] = array[s2++];
        }
        //拷贝tmp数组的元素，放入原来的数组当中
        for (int i = 0; i < k; i++) {
            array[i + low] = tmp[i];
        }
    }

    /**
     * 归并排序 - 非递归版
     * @param array
     */
    public static void mergeSort1(int[] array){
        int nums = 1;

        while (nums < array.length){
            //数组每次都要进行遍历
            for (int i = 0; i < array.length; i += nums * 2) {
                int left = i;
                int mid = left + nums - 1;
                if (mid >= array.length){
                    mid = array.length - 1;
                }
                int right = mid + nums;
                if (right >= array.length){
                    right = array.length - 1;
                }
                //下标确定之后
                merge(array, left, mid, right);
            }
            nums *= 2;//分组
        }
    }

    /**
     * 计数排序
     * 时间复杂度：O(n)
     * 空间复杂度：O(M) M:当前数据的范围：0-999
     * 适用于n个数，数据范围是0-n之间
     * 当前代码是不稳定的，本质上是稳定的
     * @param array
     */
    public static void countingSort(int[] array){
        int maxVal = array[0];
        int minVal = array[0];
        for (int i = 0; i < array.length; i++) {
            if (array[i] < minVal){
                minVal = array[i];
            }
            if (array[i] > maxVal){
                maxVal = array[i];
            }
        }
        int[] count = new int[maxVal - minVal + 1];//默认都是0
        for (int i = 0; i < array.length; i++) {
            int index = array[i];
            count[index - minVal]++;
        }
        int indexArray = 0;
        //遍历计数数组，将数据写回array
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0){
                //这里一定要加minVal, 因为不一定是0开头的值
                array[indexArray++] = i + minVal;
                count[i]--;
            }
        }
    }
    /**
     * 有序数据
     * @param capacity
     */
    public static void Random1(int capacity){
        int[] array = new int[capacity];
        for (int i = 0; i < array.length; i++) {
            array[i] = i;
        }
        long start = System.currentTimeMillis();
        //insertSort(array);
        //shellSort(array);
        //selectSort(array);
        //heapSort(array);
        //bubbleSort(array);
        quickSort(array);//对于有序数据，快排递归次数太深，栈溢出
        long end = System.currentTimeMillis();
        System.out.println(end - start);
    }

    /**
     * 无序数据
     * @param capacity
     */
    public static void Random2(int capacity){
        int[] array = new int[capacity];
        Random random = new Random();
        for (int i = 0; i < array.length; i++) {
            array[i] = random.nextInt(capacity);
        }
        long start = System.currentTimeMillis();
        //insertSort(array);
        //shellSort(array);
        //selectSort(array);
        //heapSort(array);
        //bubbleSort(array);
        quickSort1(array);
        long end = System.currentTimeMillis();
        System.out.println(end - start);
    }
    public static void main(String[] args) {
        int[] array = {12,5,9,34,6,0,33,56,89,0,7,4,55,77};
        //Random1(10_000);
        //Random2(10_00000);
        //bubbleSort(array);

        //quickSort(array);
        //System.out.println(Arrays.toString(array));
        //quickSort1(array);

        //mergeSort1(array);
        countingSort(array);
        System.out.println(Arrays.toString(array));
    }

    public static void main2(String[] args) {
        int[] arary1 = {5,8,9,11,13,24};
        int[] array2 = {6,7,8,9,12,43,56,67,90};
        int[] array = mergeArray(arary1,array2);
        System.out.println(Arrays.toString(array));
    }






































}
